import functools
class Solution(object):
    def knightDialer(self, n):
        base = 10 ** 9 + 7
        @functools.cache
        def search(k, num):
            if k == n:
                return 1
            else:
                if num == 0:
                    return (search(k + 1, 4) + search(k + 1, 6)) % base
                if num == 1:
                    return (search(k + 1, 6) + search(k + 1, 8)) % base
                if num == 2:
                    return (search(k + 1, 7) + search(k + 1, 9)) % base
                if num == 3:
                    return (search(k + 1, 4) + search(k + 1, 8)) % base
                if num == 4:
                    return (search(k + 1, 0) + search(k + 1, 3) + search(k + 1, 8)) % base
                if num == 5:
                    return 0
                if num == 6:
                    return (search(k + 1, 0) + search(k + 1, 1) + search(k + 1, 7)) % base
                if num == 7:
                    return (search(k + 1, 2) + search(k + 1, 6)) % base
                if num == 8:
                    return (search(k + 1, 1) + search(k + 1, 3)) % base
                if num == 9:
                    return (search(k + 1, 2) + search(k + 1, 4)) % base

        t = 0
        for i in range(10):
            t += search(1, i)
        return t % base

data = Solution()
n = 2
print(data.knightDialer(n))